﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val=0,ListNode next=null)
        {
            this.val = val;
            this.next = next;
        }
    }
    /*
     给定一个头结点为 head 的非空单链表，返回链表的中间结点。

    如果有两个中间结点，则返回第二个中间结点。

 

    示例 1：

    输入：[1,2,3,4,5]
    输出：此列表中的结点 3 (序列化形式：[3,4,5])
    返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    注意，我们返回了一个 ListNode 类型的对象 ans，这样：
    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

    提示：

    给定链表的结点数介于 1 和 100 之间。
     */
    public class Solution876
    {
        /// <summary>
        /// 一般解法
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public ListNode MiddleNode(ListNode node)
        {
            ListNode result=null; ;
            var nodes=new List<ListNode>();
            while (node != null)
            {
                nodes.Add(node);
                node = node.next;
            }
            var tmp=nodes.ToArray();
            var count=tmp.Length;
            var index = count / 2;

            result = tmp[index];
            return result;
        }
        public ListNode MiddleNode1(ListNode head)
        {
            ListNode aNode = head;
            ListNode bNode = head;
            while(bNode != null && bNode.next!=null)
            {
                aNode=aNode.next;
                bNode=bNode.next.next;
            }
            return aNode;
        }
    }
}
